package com.asia.algorithmcode.backTracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 131、分割回文串
 */
public class Partition {


    public static void main(String[] args) {
        String s = "aab";
        List<List<String>> partition = new Partition().partition(s);
        partition.forEach(System.out::println);
    }

    int n;
    List<String> ans = new ArrayList<>();
    List<List<String>> res = new ArrayList<>();
    boolean[][] f;


    public List<List<String>> partition(String s) {
        n = s.length();
        // f[i][j] 表示从i到j是否是一个回文字符串
        f = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(f[i], true);
        }
        for (int i = n; i >= 0; --i) {
            for (int j = i + 1; j < n; j++) {
                // s的i位置与j位置字符相等，且i+1到j-1也是回文串，则从i到j也是回文串
                f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
            }
        }
        dfs(s, 0);
        return res;
    }

    private void dfs(String s, int i) {
        if (i == n) {
            res.add(new ArrayList<>(ans));
            return;
        }
        for (int j = i; j < n; j++) {
            if (f[i][j]) {
                ans.add(s.substring(i, j + 1));
                dfs(s, j + 1);
                ans.remove(ans.size() - 1);
            }
        }
    }
}
